On finding optimal and near-optimal lineal spanning trees

The search for good lineal, or depth-first, spanning trees is an important aspect in the implementation of a wide assortment of graph algorithms. We consider the complexity of findingoptimal lineal spanning trees under various notions of optimality. In particular, we show that several natural problems, such as constructing a shortest or a tallest lineal tree, are NP-hard. We also address the issue of polynomial-time, near-optimization strategies for these difficult problems, showing that efficient absolute approximation algorithms cannot exist unlessP = NP.This author's research was supported in part by the Sandia University Research Program and by the National Science Foundation under Grant M IP-8603879.This author's research was supported in part by the National Science Foundation under Grants ECS-8403859 and MIP-8603879.     

Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

Age effects in coding tasks: Componential analysis and test of the sensory deficit hypothesis.

Multiple forms of a symbol-digit substitution task were used to provide a componential analysis of age differences in coding task performance. The results demonstrated age differences in feature encoding, memory, and visual search. A 2nd experiment was conducted with young adults to investigate a sensory deficit as a locus of age differences. The spatial contrast sensitivity deficit of older adults was simulated on forms by applying a digital filter. Persons in the age-simulated contrast condition performed worse than those in the normal contrast condition. The stimulus degradation effect was linked to visual search speed. The study illustrates the utility of componential analysis and offers direct support for the hypothesis that sensory deficits affect performance on tasks used to assess intelligence (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Plasticity of feature-based selection in triple-conjunction search.

Two experiments examined the disruption of feature-based selection in triple-conjunction search at multiple target transfers. In Experiment 1, after 10 training sessions, a new target possessing previous distractor features was introduced. This produced disruption in RT and fixation number, but no disruption in feature-based selection. Specifically, there was a tendency to fixate objects sharing the target's contrast polarity and shape and this did not change even upon transfer to the new target. In Experiment 2, 30 training sessions were provided with three target transfers. At the first transfer, the results replicated Experiment 1. Subsequent transfers did not produce disruption on any measure. These findings are discussed in terms of strength theory, Guided Search, rule-based approaches to perceptual learning, and the area activation model. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Integration of batching and scheduling for hot rolling production in the steel industry

This paper investigates the hot rolling production scheduling problem in the steel industry and proposes a new mixed integer programming model for this problem based on the monolithic modeling strategy that integrates batching and scheduling. Using this strategy, the new model can simultaneously schedule multiple turns and simultaneously determine the production timetable of these turns in a global optimal view. A long-term tabu search heuristic using frequency-based memory is developed to obtain near-optimal solutions for this problem. Three kinds of speed-up strategies are developed to accelerate the search procedure of the proposed tabu search. A practical scheduling system combining the proposed mathematical model and the tabu search heuristic has been developed and tested on instances collected from practical production data. The experimental results show that the proposed mathematical model and the tabu search heuristic outperform both the current manual scheduling method and the traditional serial method.     

感应电机压频比调节的模糊节能控制

根据三相感应电机的等效电路，推导出电机的损耗和输出功率与压频比之间的关系，提出了压频比调节的节能控制方法。考虑电机不同负载时损耗曲线的变化持点，引入基于电机转速和输入功率的比例算子，对电机输入功率的变化进行量化；电机稳态运行时进行模糊自寻优控制，动态调速时进行较高的恒压频比控制，提高了电机的效率并保持了一定的动态响应特性。仿真结果验证了运行控制方案的可行性和有效性。     

空气钻井条件下录井工艺方法与技术配套探讨

针对玉门青西油田深部高陡易斜地层存在可钻性差、自然造斜能力强，致使钻井周期长、成本高等特点，中油集团公司在吐哈油田设立钻探“工程探索井（L14井）”重大科研项目，试验研究空气钻井技术。根据L14井录井的实际情况，首先分析了空气钻井条件对录井带来的影响和常规的录井工艺方法和技术设备存在的不足；从5个方面介绍了录井工艺、技术方法的改进，探讨了空气钻井下的岩屑上返理论；介绍了配置装备的改进，分析了该井录井配套技术的应用效果。从该试验井的录井效果看，经改进的录井工艺、方法及装备基本上能满足空气钻井的需要，取全取准了地质及工程资料，为地质解释和评价提供了可靠依据；在工程监测、保障施工安全方面，工程录井也发挥了作用。但综合录井仪软件及后台评价程序还不适应空气钻井的需要，相关的理论研究及工艺完善还有许多课题尚需深入。     

基于神经网络的智能检索系统

文章首先概述了当前大多数的搜索引擎的主要的弊端；然后着重介绍了智能检索系统的运行基本思路和售用算法，以及该算法在检索领域中运用的优点；最后指出，神经网络运用在检索领域，可解决网络管理中的诸多难题。     

Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times

In this article we study thetabu search (TS) method in an application for solving an important class of scheduling problems. Tabu search is characterized by integrating artificial intelligence and optimization principles, with particular emphasis on exploiting flexible memory structures, to yield a highly effective solution procedure. We first discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. A prototype TS method is developed for this problem using the common approach of exchanging the position of two jobs to transform one schedule into another. A more powerful method is then developed that employs insert moves in combination with swap moves to search the solution space. This method and the best parameters found for it during the preliminary experimentation with the prototype procedure are used to obtain solutions to a more complex problem that considers setup times in addition to setup costs. In this case, our procedure succeeded in finding optimal solutions to all problems for which these solutions are known and a better solution to a larger problem for which optimizing procedures exceeded a specified time limit (branch and bound) or reached a memory overflow (branch and bound/dynamic programming) before normal termination. These experiments confirm not only the effectiveness but also the robustness of the TS method, in terms of the solution quality obtained with a common set of parameter choices for two related but different problems.     

Optimal search for signals in a multichannel system: Arbitrary initial distribution in state space merging scheme

Markovian and semi-Markovian random processes are used to analyze the problem of optimal search for signals in a multichannel communication system with arbitrarily distributed random outputs. The search efficiency factor is found in explicit form based on state space merging, and a mathematical programming problem is set up to find a numerical suboptimal solution. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 144–150, May–June 2007.